package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;

/*
    给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目。
 */
public class Leetcode2171 {

    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans);
        int len= beans.length;
        long total=0;
        for (int bean : beans) {
            total += bean;
        }
        long max=0;
        for (int i = 0; i < len; i++) {
            long cur=(long) beans[i]*(len-i);
            if(max<cur){
                max=cur;
            }
        }
        return total-max;
    }

    public static void main(String[] args) {
        Leetcode2171 res=new Leetcode2171();
        //res.minimumRemoval(new int[]{4,1,6,5});
        System.out.println(res.minimumRemoval(new int[]{60}));
        System.out.println(res.minimumRemoval(new int[]{66, 90, 47, 25, 92, 90, 76, 85, 22, 3}));
    }
}
